The present invention pertains to a memory system with a non-volatile memory. In particular, the present invention relates to a memory system having an address translating function for translating the logical address given to access the non-volatile memory to a physical address.
In recent years, as a memory system for storing a variety of digital information represented by image data or music data, there has been widely known a memory card with a rewritable non-volatile memory in which, even if a power supply is turned OFF, stored information is not erased.
A typical example of such rewritable non-volatile memory includes a NAND type flash memory. A flash memory of such type is managed in blocks. In this memory, information is erased in blocks. The information is erased by an operation for writing data of xe2x80x9c1xe2x80x9d into all bits contained in blocks. In addition, a logical block address is allocated to one block. Each block consists of a plurality of sectors. Each of these sectors is a minimum unit for read/write operation in a flash memory, and consists of 512 bytes, for example. Each sector has a redundant section other than a data section. A logical block address allocated to a block to which the corresponding sector belongs is registered in a predetermined field of this redundant section.
An address translation table (an address translation mechanism) for translating a logical address to a physical address of the flash memory is required to access the flash memory. A reason required for this address translation is stated below. Namely, this is because, even if a fault block occurs in the flash memory, and is substituted by another empty block, a host system can provide access to a target block with the same logical address irrespective of the presence or absence of such substitution without worrying about the above fault and substitution.
The number of entries in the above address translation table coincides with the number of blocks in a flash memory. For example, in the case where one sector consists of 512 bytes, namely 0.5 KB (kilobytes), and a block consists of 32 sectors, i.e., in the case where a 16 MB (megabyte) flash memory having 16 KB in one block is employed, the number of entries in an address translation table is 16 MB/16 KB=1 K=1,024. The address translation table is generally employed by storing the table in an area (a RAM area) secured on RAM that is a volatile memory. Therefore, in the above example, assuming that one entry is 2 bytes, the RAM area required to store the address translation table is 2 KB.
On the other hand, there has been recently increased the storage capacity of a flash memory with advancement of semiconductor manufacturing technology. For example, there has been introduced a 32 MB flash memory in which the number of blocks is 2,048 and one block consists of 16 KB or a 64 KB flash memory in which the number of blocks is 4,096, and one block consists of 16 KB, and further, a 256 MB flash memory in which the number of blocks is 16,384, and one block consists of 16 KB.
If the storage capacity of the flash memory increases, a RAM area for holding an address translation table must be increased. For example, in the case of a 32 MB flash memory, a 64 MB flash memory, and 256 MB flash memory, a 4 KB RAM area, a 8 KB RAM area, and a 32 KB RAM area are required for the address translation table, respectively. Namely, a RAM area which is twice, four times, and 116 times as large as the 16 MB flash memory is required.
Thus, in a conventional memory card with a rewritable non-volatile memory represented by a flash memory, if the storage capacity of the memory increases, there must be increased an area of a volatile memory represented by a RAM required to hold an address translation table.
The present invention has been made in view of the foregoing circumstance. It is an object of the present invention to provide a memory system free of increasing a volatile memory area for an address translation table even if the storage capacity of a non-volatile memory increases.
In order to achieve the aforementioned object, there is provided a memory system comprising: a non-volatile memory storing a plurality of address translation tables to translate into a physical address a logical address given to access the non-volatile memory; a volatile memory having an address translation table area for storing at least one table fewer than the total number of the tables from among the plurality of address translation tables on the non-volatile memory; and means for translating a logical address to a physical address. The address translation tables are associated with their different logical address ranges. When a logical address is given for accessing the non-volatile memory, the translating means translates the logical address into a physical address by utilizing the address translation table corresponding to the logical address on the volatile memory.
In the thus configured memory system, when a logical address is given for accessing a non-volatile memory, address translation for translating the logical address to a physical address is performed by utilizing the address translation table corresponding to the logical address on the volatile memory.
In this manner, in the present invention, at least one table rather than all of the address translation tables on the non-volatile memory is placed on a volatile memory, and the address translation tables on the volatile memory are employed for address translation from a logical address to a physical address. Thus, unlike a case in which all address translation tables are placed on a volatile memory, even if the capacity of the non-volatile memory is increased, it becomes possible to suppress an increase in storage capacity of the volatile memory.
When the address translation table placed on the volatile memory are not the address translation table corresponding to the logical address ranges to which the given logical addresses belong, address translation cannot be performed. The memory system according to the present invention further comprises: means for, when a logical address is given for accessing a non-volatile memory, determining whether the address translation table corresponding to the logical address range to which the logical address belong to exists on the volatile memory; and means for, when it is determined by the determining means that the corresponding address translation table does not exist on the volatile memory, copying the address translation table from a non-volatile memory to the address translation table area on the volatile memory, thereby replacing an original address translation table on the address translation table area.
In the thus configured memory system, when an address translation table required to translate a given logical address into a physical address does not exist in the table area, that is, in the case of table mis-hit the table is copied immediately from the non-volatile memory to the table area, and the original address translation table on the address translation table area is replaced on the address translation table. Therefore, even in the case of table mis-hit, translation from a given logical address to a physical address can be performed speedily. In the meantime, when video data or voice data is read (reproduced) consecutively from a flash memory upon a request from a host system, it is general that a logical address given from the host system is consecutive. Therefore, replacement of the address translation table does not occur frequently due to data reading of such type. It is possible to translate a logical address to a physical address speedily by utilizing the table with respect to the logical addresses that belong to the logical address ranges corresponding to the address translation tables copied to the table area.
For a better understanding of usefulness of the above configuration according to the present invention, there is considered a case in which a configuration is adopted to sequentially generate a required address translation table to be held on the table area without providing each of the address translation tables in a non-volatile memory, which is different from the present invention. In this case, during table mis-hit in which there does not exist a table required for the target address translation on the table area, the required table must be generated again. Therefore, as is the case with video data or voice data reading, a case in which real time use is required is problematic. Namely, the penalty during table mis-hit is great. In order to avoid this, it is considered that all tables are held in the table area, however, the storage capacity of a volatile memory is significantly increased. In contrast, according to the present invention, all address translation tables are provided in the non-volatile memory. Thus, even if a table mis-hit occurs, the required address translation table is copied from the non-volatile memory to the table area of the volatile memory, thereby making it possible to perform address translation processing speedily, the penalty during table mis-hit is reduced. Therefore, in the present invention, even if a volatile memory with its small capacity is employed, namely, even if a table area of its sufficient size cannot be allocated, it becomes possible to reduce the penalty during table mis-hit, and application to real time use can be achieved. In the present invention, it is required to allocate an area for storing all address translation tables on the non-volatile memory. However, the capacity of the non-volatile memory is extremely larger than that of the volatile memory, which is not problematic unlike a configuration in which all tables are placed on the volatile memory.
Logical addresses are provided, each including a logical block address which has a specific field. Like the conventional ones, the non-volatile memory comprises a plurality of blocks to which the logical block addresses are allocated. The address translation tables, the determining means, and the translating means may be configured as follows.
Each address translation table is provided for a group of blocks provided on the memory. Each group of blocks corresponds to a range of logical addresses. The same data item is contained in the specific fields of the logical block addresses included in the logical addresses of any group. The data item designates the group of blocks, which corresponds to the range of logical addresses.
Each address translation table has a group of entries that can be designated by the logic block addresses allocated to the blocks of the group corresponding to the group of entries. Each entry is provided for registering physical address information that represents a location in the non-volatile memory.
The determining means determines whether an address translation table exists on the non-volatile memory, the address translation table corresponding to the range of logical addresses which is designated by the data item contained in the specific field of the logical block address included in the given logical address.
The translating means refers to the corresponding entry in the address translation table provided on the volatile memory in accordance with the logical block addresses contained in the given logical address, thereby translating the logical address to a corresponding physical address. More specifically, the translating means translates the logical address to physical address immediately if the determining means determines that an address translation table exists on the volatile memory. If the determining means determines that no address translation table exists on the volatile memory, the translating means translates the logical address to a corresponding physical address after the copying means has copying the address translation table onto the volatile memory.
It is desirable to use a rewritable non-volatile memory as the non-volatile memory. In this case, only empty address translation tables are first provided without presetting the contents of each entry in each of the address translation tables, and then, a configuration in which the contents of entries are set as required may be applied. In this configuration, registering means is provided. When physical address information is not registered in address translation table entry referred to by the translating means, the registering means searches for an empty block on the non-volatile memory, and allocates the logical block address in the given logical address to the block. Then, physical address information of the block is written into the entry referred to and the corresponding entry in the address translation table on the non-volatile memory. In this manner, the information on entries in the address translation table, corresponding to blocks which may be used infrequently can be eliminated from being registered.
In addition, when a block error occurs as a result of writing into the non-volatile memory employing a physical address translated by the translating means, the substituting means is added so as to correct the block error. This substituting means searches for an empty block on the non-volatile memory, and allocates the logical block address in the given logical address to the block. The substituting means updates the entry referred to and the corresponding entry in the address translation table on the non-volatile memory based on the physical address information on the block. In this manner, even if a block error occurs during writing, block substituting processing can be performed reliably.
In the present invention, the non-volatile memory can be managed in units of zones each consisting of group of blocks to which logical block addresses are allocated, respectively, which belong to a logical address range and which have each a specific field containing the same data item. In this case, one of the zones has been allocated to a system area in which system management information is to be stored. In this configuration, each of these address translation tables is stored in any one block in the corresponding zone of the non-volatile memory, and the copying means may include the following first and second copy functions. The first copy function is directed to a function for, during startup of the memory system, copying into the address translation table area of the non-volatile memory an address translation table stored in at least one zone other than a zone allocated to the system area of each of the zones of the non-volatile memory and an address translation table stored in the zone allocated to the system area. The second copy function is directed to a function for, when it is determined by the determining means that the corresponding address translation table does not exist on the non-volatile memory, replacing any one address translation table other than the address translation table corresponding to the system area with the corresponding address translation table. In such configuration, the address translation table corresponding to the system area can reside in a volatile memory. Thus, even if the storage capacity of the non-volatile memory increases, while an increase in the capacity of the volatile memory is prevented, an occurrence of a table mis-hit is always restrained for an access request for a frequently accessed system area, whereby fast address translation can be achieved. In addition, a penalty in the case of a table mis-hit is reduced to the minimum for an access request for an area other than system area, thereby making it possible to cope with real time use.
If the non-volatile memory is managed in units of zones, the redundant sections of the sectors constituting each block may include flag fields storing flag information. The flag information indicates one of three use states of the blocks. In the first state, the blocks are used to store a valid address translation table. In the second state, the blocks are used to store an invalidated address translation table. In the third state, the blocks are used to store valid data other than an address translation table.
In addition, in a configuration in which the aforementioned non-volatile memory is managed in units of zones, allocating means, registering means, and update means are provided. In the allocating means, when physical address information is not registered in an entry of the address translation table on the volatile memory referred to by the translating means, an empty block is searched for a zone in which the address translation table on the non-volatile memory corresponding to the table is stored, and a logical block address included in the given logical address is allocated to the block. In the registering means, physical address information on a block to which a logical block address is allocated by the allocating means is written into an entry of the address translation table on the volatile memory referred to by the translating means. In the update means, an empty block is searched for in a zone in which stored the address translation table on the non-volatile memory corresponding to the address translation table on the volatile memory referred to by the translating means is stored. Then, the address translation table in which physical address information has been written by the registering means is written in a predetermined area in the block. The update means sets flag information indicating the first state, in the flag field of the redundant section of each sector provided in the predetermined area in which an address translation table has been written. The update means sets the flag information indicating the second state in the flag field of the redundant section of one sector provided in the predetermined area in which an address translation table has been written, this address translation table corresponding to the address translation table and provided on the non-volatile memory. In such configuration, writing into the same block can be prevented from being concentrated.
In addition, in a configuration in which the aforementioned non-volatile memory is managed in units of zones, in addition to the allocating means, the registering means and the update means, there is provided detecting means and substituting means. In the substituting means, when an occurrence of a block error is detected by the detecting means, an empty block is searched for in the same manner as that in the update means, and a logical block address in the given logical address is allocated to the block. Then, the entry referred to in the address translation table on the above volatile memory is updated based on physical address information of the block. When the entry referred to in the address translation table on the volatile memory is updated by the substituting means, in the update means, an empty block is searched for, and the address translation table in which the entry referred to has been updated is written into a predetermine area in the block. In the update means, flag information indicating the first state is set in the flag field of the redundant section of each sector in an area in which the address translation table has been written, and flag information indicating the second state is set in the flag field of the redundant section of each sector in an area in which the original address translation table on the non-volatile memory has been stored. In such configuration, writing into the same block can be prevented from being concentrated.
By each of the zones for the non-volatile memory, an assignment table containing flag information indicating, for each block in the zone whether the block is used may be paired with the address translation table. A pair of the assignment table and the address translation table is stored in the same block in the corresponding zone. In addition, in the volatile memory, there is allocated an assignment table area for storing the assignment table consisting of a pair of the plural address translation tables on the non-volatile memory stored in the address translation table area. Therefore, if an empty block is searched for by referring to the assignment table on this assignment table area in a predetermined direction, the frequency of writing into each block in the zone can be uniformed.
Additional objects and advantages of the invention will be set forth in the description which follows, and in part will be obvious from the description, or may be learned by practice of the invention. The objects and advantages of the invention may be realized and obtained by means of the instrumentalities and combinations particularly pointed out hereinafter.